package LeetCode._02_数组;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/*
    count[i] = Count(j) where j > i and nums[j] < nums[i]
    每当执行 nums[p] = temp[i]时，也就是temp[i]<temp[j],或者j == hi + 1的时候，
    就可以确定temp[i]这个元素后面比他小的元素个数为 j - mid - 1
 */
public class _315_计算右侧小于当前元素的个数 {
    //每个元素的索引位置会不断改变，
    //所以我们用一个 Pair 类封装每个元素及其在原始数组 nums 中的索引，以便 count 数组记录每个元素之后小于它的元素个数。
    class Pair{
        int val,id;
        public Pair(int val,int id){
            this.val = val;
            this.id = id;
        }

    }

    private Pair[] temp; //辅助数组,进行比较
    private int[] count; //记录每个元素后面比自己小的元素个数

    public List<Integer> countSmaller(int[] nums) {
        if(nums == null || nums.length == 0) return new ArrayList<>();
        int n = nums.length;
        temp = new Pair[n];
        count = new int[n];
        Pair[] arr = new Pair[n]; //代替nums数组
        for(int i=0;i<n;++i){
            arr[i] = new Pair(nums[i],i);
        }

        // 执行归并排序，本题结果被记录在 count 数组中
        sort(arr,0,n-1);
        List<Integer> res = new LinkedList<>();
        for (int num : count) {
            res.add(num);
        }
        return res;
    }


    //对给定nums[lo..hi]进行排序
    private void sort(Pair[] arr,int lo,int hi){
        if(hi == lo) return;

        int mid = lo + (hi - lo) / 2;

        sort(arr,lo,mid);
        sort(arr,mid+1,hi);

        merge(arr,lo,mid,hi);
    }

    //将数组nums[lo..mid]和nums[mid+1...hi]合并
    private void merge(Pair[] arr,int lo,int mid,int hi){
        for(int i=lo;i<=hi;i++){
            temp[i] = arr[i];
        }
        int i = lo,j = mid + 1;
        for(int p = lo;p<=hi;p++){
            if(i == mid + 1){
                //左半部分已经比完，右半部分按照升序排列,右侧没有元素小于当前元素
                arr[p] = temp[j++];
            }else if(j == hi + 1){
                arr[p] = temp[i++];
                //更新count数组,当前元素的索引未arr[p].id 加上 j - mid - 1,就是比他小的元素的个数
                count[arr[p].id] += j - mid - 1;
            }else if(temp[i].val>temp[j].val){
                arr[p] = temp[j++];
            }else{
                arr[p] = temp[i++];
                //更新count数组,当前元素的索引未arr[p].id 加上 j - mid - 1,就是比他小的元素的个数
                count[arr[p].id] += j - mid - 1;
            }
        }
    }
}
